1. Technical Field
The invention relates generally to computing systems, and more particularly to systems and methods for detecting dependencies between processor load/store instructions in multiple phases in order to increase the performance of high speed processors.
2. Related Art
Often, the order of execution of a sequence of instructions by a processor is changed in order for the processor to execute the instructions more efficiently. For example, in the case of a processor that can execute two types of instructions concurrently, the processing efficiency of the processor can be increased by supplying the processor with a sequence of alternating types of instructions. If a large number of consecutive instructions of the first type is received, the processors will be underutilized since only approximately half of the processor will be used.
Changing the order of execution of the instructions can optimize the execution of the instructions but can create other execution problems. For example, if a load instruction that depends on a preceding store instruction is moved ahead of the store instruction, this may result in the load instruction reading invalid data. It is therefore necessary to detect such dependencies in order to be able to avoid such problems.
Several techniques can be employed to detect load/store instruction dependencies and avoid the executing instructions in an order that would result in the use of invalid data. Upon successful detection of a load/store dependency, the execution of dependent instruction may be held until the execution of any instructions on which the instruction depends is complete. Many of the available techniques involve the comparison of the memory addresses referenced by younger and older instructions. If two load/store instructions are reading from and writing to the same address, a potential dependency exists between the instructions.
Performing a full address comparison on all the instructions in an instruction sequence, however, is becoming exceedingly difficult. As memory sizes increase, longer addresses are required to reference memory locations and more time is required to perform comparisons between the addresses. In addition, today's high-speed processors have critical timing specifications. In regard to pipelined processors in particular, there may be only a small amount of time between stages in the pipeline, so it may be especially difficult to perform full address comparisons between stages in the pipeline.
To overcome the timing issue, some systems perform only a partial address comparison. Since only a portion of the addresses is compared, it becomes more probable that the operation can be completed within the imposed time limits. A partial address comparison, however, can falsely identify dependencies between load/store instructions even when dependencies do not actually exist. This is because, while the compared portions of the addresses may match, the remainder of the addresses may not. If the addresses are mistakenly determined to be the same, the corresponding instructions may mistakenly be determined to be dependent, causing the later of the instructions to be suspended. As a result of the unnecessary suspension of load/store instructions caused by the false identification of the partial comparison, the efficiency of the processor is decreased.
It would therefore be desirable to provide systems and methods to reduce the number of falsely identified load/store dependencies between instructions. Moreover, it would be desirable for these systems and methods to be able to operate within the limited time between instruction stages of modern, high-speed processors without delaying the execution of instructions by the processors.